package algorithm.dynamicProgramming.leetcode;

import java.util.Arrays;

//198. 打家劫舍
//213. 打家劫舍 II
public class Rob {
    public static void main(String[] args) {
        int[] data = {1, 2, 3, 1, 5};
//        System.out.println(rob(data));
        rob(data);
    }

    public static int rob(int[] nums) {


        int[] f = new int[nums.length + 1];
        f[0] = 0;
        f[1] = nums[0];
        for (int i = 2; i <= nums.length; i++) {
            f[i] = Math.max(f[i - 1], f[i - 2] + nums[i - 1]);
        }
        System.out.println(Arrays.toString(f));
        return f[nums.length];
    }

    public static int rob2(int[] nums) {
        int n = nums.length;
        int[] f1 = new int[n + 1];
        int[] f2 = new int[n + 1];
        f1[0] = 0;
        f2[0] = 0;
        f1[1] = nums[0];

        //最后一个不偷
        for (int i = 2; i <= n; i++) {
            if (i != n) {
                f1[i] = Math.max(f1[i - 1], f1[i - 2] + nums[i - 1]);
            } else {
                f1[i] = Math.max(f1[i - 1], f1[i - 2]);
            }
        }
        for (int i = 2; i <= n; i++) {
            f2[i] = Math.max(f2[i - 1], f2[i - 2] + nums[i - 1]);
        }
        return Math.max(f1[n], f2[n]);

    }

    public static int rob21(int[] nums) {
        int[][] f = new int[nums.length + 1][2];
        f[0][0] = 0;
        f[1][0] = nums[0];
        f[1][1] = 0;
        for (int i = 2; i <= nums.length; i++) {
            f[i][0] = Math.max(f[i - 1][0], f[i - 2][0] + nums[i - 1]);
            f[i][1] = Math.max(f[i - 1][1], nums[i - 1] + f[i - 2][1]);
        }
        return Math.max(f[nums.length - 1][0], f[nums.length][1]);
    }


    /**
     * 二战dp
     */
    public int robP(int[] nums) {
        int n = nums.length;
        int[] f1 = new int[n + 1];
        int[] f2 = new int[n + 1];
        // 初始化值
        f1[0] = 0;
        f2[0] = 0;
        f1[1] = nums[0];


        // 状态转义方程
        // 第一个偷，最后一个不偷
        for (int i = 2; i <= n; i++) {
            if (i != n) {
                f1[i] = Math.max(f1[i - 1], f1[i - 2] + nums[i - 1]);
            } else {
                f1[i] = Math.max(f1[i - 1], f1[i - 2]);
            }

        }
        // 不偷第一个，最后一个偷 ,f2[1]=0
        for (int i = 2; i <= n; i++) {
            f2[i] = Math.max(f2[i - 1], f2[i - 2] + nums[i - 1]);
        }
        return Math.max(f1[n], f2[n]);
    }
}
